#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>

std::vector<char> concat(const std::vector<char> &vec1,
                         const std::vector<char> &vec2) {
    std::vector<char> result;
    result.insert(result.end(), vec1.begin(), vec1.end());
    result.insert(result.end(), vec2.begin(), vec2.end());
    return result;
}

struct GraphNode {
    char val;
    std::vector<GraphNode *> neighbors;
    GraphNode(char v = '\0') : val(v) {}
};

std::vector<char> bfs(GraphNode *root) {
    std::vector<char> result;
    if (!root) {
        return result;
    }
    std::queue<GraphNode *> q;
    std::set<GraphNode *> visited;
    visited.insert(root);
    q.push(root);

    while (!q.empty()) {
        auto current = q.front();
        q.pop();
        result.push_back(current->val);
        for (auto neighbor : current->neighbors) {
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }

    return result;
}

void dfs(GraphNode *root, std::vector<char> &result,
         std::set<GraphNode *> &visited) {
    if (!root) {
        return;
    }
    visited.insert(root);
    result.push_back(root->val);
    for (auto neighbor : root->neighbors) {
        if (visited.find(neighbor) == visited.end()) {
            visited.insert(neighbor);
            dfs(neighbor, result, visited);
        }
    }
}

std::vector<char> dfs(GraphNode *root) {
    std::set<GraphNode *> visited;
    std::vector<char> result;
    dfs(root, result, visited);
    return result;
}

std::string substr(const std::string &str, int &idx) {
    int start_pos = idx;
    int left_cnt = 0;
    char ch = str[idx++];
    do {
        if (ch == '(') {
            left_cnt++;
        } else if (ch == ')') {
            left_cnt--;
        }
        if (left_cnt == 0 && ch == ',') {
            break;
        }
        ch = str[idx++];
    } while (idx < str.size());
    return str.substr(start_pos, idx - start_pos - 1);
}

GraphNode *initGraph(const std::string &str) {
    int size = str.size();
    if (size == 0) {
        return nullptr;
    }
    int idx = 0;
    char ch = str[idx++];
    GraphNode *root = new GraphNode(ch);
    ch = str[idx++];
    if (ch == '(') {
        do {
            if (ch == ',') {
                ch = str[idx++];
                continue;
            }
            auto sstr = substr(str, idx);
            root->neighbors.push_back(initGraph(sstr));
            ch = str[idx];
        } while (idx < size);
    }

    return root;
}

void printResult(const std::vector<char> &result,
                 const std::string &perfix = "") {
    if (perfix.size() > 0) {
        std::cout << perfix;
    }
    int size = result.size();
    for (int i = 0; i < size; i++) {
        std::cout << result[i];
        if (i != size - 1) {
            std::cout << "-->";
        } else {
            std::cout << std::endl;
        }
    }
}

void destroyGraph(GraphNode *root) {
    if (!root) {
        return;
    }
    for (auto &neighbor : root->neighbors) {
        destroyGraph(neighbor);
    }
    delete root;
    root = nullptr;
}

int main() {
    std::string gstr("A(B(D,E),C(F))");
    auto *graph = initGraph(gstr);
    printf("graph = %p\n", graph);
    auto bfs_result = bfs(graph);
    printf("graph = %p\n", graph);
    auto dfs_result = dfs(graph);
    printResult(bfs_result, "BFS: ");
    printResult(dfs_result, "DFS: ");
    destroyGraph(graph);
    return 0;
};
